With advances in digital imaging systems, using matting techniques to create novel composites or to facilitate other editing tasks has gained increasing interest from both professionals as well as consumers. Matting refers to the problem of accurate foreground extraction from images and video. Specifically, an observed image may be modeled as a convex combination of a foreground image and a background image, using alpha values in an alpha matte as interpolation coefficients. The alpha matte may be used as a soft mask to apply a variety of object-based editing functions. In particular an alpha matte may be used to separate a foreground object from the background of an input image. An input image I, as depicted in FIG. 1A, may be modeled as a linear combination of a foreground image F and a background image B using alpha matte a:I=α·F+(1−α)·B 
FIG. 1B illustrates an alpha matte corresponding to the lion in the foreground of the image of FIG. 1A. The alpha matte contains an alpha value corresponding to each pixel of the input image. For example, the maximum α value for a pixel may be 1, meaning that the pixel is fully occupied by the foreground. The minimum value may be 0, meaning that the pixel is not covered by the foreground at all. An α value between 0 and 1 may indicate that the pixel is semi-transparent, meaning that the foreground and the background both contribute to the appearance (e.g. color) of the pixel.
Using an alpha matte to compose a foreground object from a first image onto a second background image may result in undesirable color from the background of the first image appearing in the composite image with the second background. For example, composing an image with the lion from the foreground of FIG. 1A onto the background of FIG. 1C may begin with the pixels representing the lion. These pixels are obtained by multiplying the alpha matte for the foreground object (i.e. the lion) with the image I. Mathematically, this is represented as αI. Using the equation above with αI as the foreground and the new background (represented as B2) gives a formula for the composite image I2:I2=αI+(1−α)B2 
Substituting the expression for I into the equation above gives:I2=α(αF+(1−α)B)+(1−α)B2=α2F+α(1−α)B+(1−α)B2 
For a pixel with an alpha matte value of 1, meaning that the pixel is completely a foreground pixel, α2 is 1 and (1−α) is 0. The entire contribution to the final image thus comes from the term α2F. For a pixel with an alpha matte value of 0, meaning that the pixel is entirely a background pixel, the term α(1−α)B has a value of 0 so the entire contribution to the pixel is from the background B2. However, for pixels with an alpha matte value between 0 and 1 neither α nor (1−α) has a value of 0 and there is a contribution to the final image I2 from both B and B2.
FIG. 1D illustrates the visual effect of the α(1−α)B term in an image. The dark line along the edge of the lion's mane in the enlarged portion of FIG. 1D represents pixels that may have a color contribution from the background of FIG. 1A. Assuming that the background of FIG. 1A is green, the edge of the lion's mane in FIG. 1D may have a greenish tinge. This may be undesirable or unacceptable in the composite image.
One method for approximating foreground and background portions of an image using global optimization is formulated mathematically as:
      min    ⁢                  ∑                  i          ∈          I                    ⁢                        ∑          c                ⁢                                  ⁢                              (                                                            α                  i                                ⁢                                  F                  i                                            +                                                (                                      1                    -                                          α                      i                                                        )                                ⁢                                  B                  i                                            -                              I                t                                      )                    2                      +                          α                  i          x                            ⁢          (                                    (                          F                              i                x                                      )                    2                +                              (                          B                              i                x                                      )                    2                    )        +                          α                  i          y                            ⁢                  (                                            (                              F                                  i                  y                                            )                        2                    +                                    (                              B                                  i                  y                                            )                        2                          )            .      
In this formula, Fi and Bi represent the foreground and background colors, respectively, to be estimated for pixel i. The first term in this energy function tends to make the estimated colors satisfy the compositing function given above. When the second term, involving the horizontal derivative of α (αix) at the location of the pixel, is large then the derivatives of the foreground and background colors, Fix and Bix, should be small. This will mean that the colors should stay smooth across an edge. The third term applies the same concept to the vertical derivatives.
The technique requires a global optimization process to solve all pixel colors simultaneously. Furthermore, the optimization process must be applied in all color channels. This process may be computationally infeasible, particularly for high resolution images with many pixels.